package codeRandomThoughts.Test106从中序与后序遍历序列构造二叉树;

import codeRandomThoughts.utils.TreeNode;


//二刷 优化算法
public class Solution4 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return myBuildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    public TreeNode myBuildTree(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        //递归数组为空代表遍历到了空结点
        if (inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd]);
        //找到根元素在inorder中的位置
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == postorder[postEnd]) {
                root.left = myBuildTree(inorder, inBegin, i - 1, postorder, postBegin, postBegin + i - 1 - inBegin);
                root.right = myBuildTree(inorder, i + 1, inEnd, postorder, postBegin + i - inBegin, postEnd - 1);
                return root;
            }
        }
        return root;
    }
}
